#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
using namespace std;
#define int long long
#define pii pair<long long,long long>
const long long INF = 0x3f3f3f3f3f3f3f3f;



signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

//void solve() {
//	cin >> a >> b >> x;
//	if (a == x || b == x) {
//		cout << "YES\n";
//		return;
//	}
//	if (a == b || a == 0 || b == 0) {
//		cout << "NO\n";
//		return;
//	}
//	if (a < b) {
//		swap(a, b);
//	}
//	if (a < x && b>x || b < x && a>x) {
//		cout << ((a - x) % b == 0 ? "YES\n" : "NO\n");
//	}
//	else {
//		while (a > x || b > x) {
//			if (a < b) {
//				swap(a, b);
//			}
//			a = a % b;
//			swap(a, b);
//			if (a == x || b == x) {
//				cout << "YES\n";
//				return;
//			}
//			if (a == 0 || b == 0) {
//				cout << "NO\n";
//				return;
//			}
//			if (a < x && b>x || b < x && a>x) {
//				cout << ((a - x) % b == 0 ? "YES\n" : "NO\n");
//				return;
//			}
//		}
//		cout << "NO\n";
//	}
//}

//int k, x;
//
//int C(int q) {
//	return (q * (q + 1)) / 2;
//}
//
//bool check1(int m) {
//	return C(m) >= x;
//}
//
//bool check2(int m) {
//	return C(k - 1) - C(2 * k - 1 - m) >= x;
//}
//
//void solve() {
//	cin >> k >> x;
//	if (x > C(k) + C(k - 1)) {
//		cout << 2 * k - 1 << '\n';
//		return;
//	}
//	int l = 1, r = k + 1, mid;
//	while (l < r) {
//		mid = (l + r) >> 1;
//		if (check1(mid)) {
//			r = mid;
//		}
//		else {
//			l = mid + 1;
//		}
//	}
//	if (l <= k) {
//		cout << l << '\n';
//		return;
//	}
//	x -= C(k);
//	l = k + 1, r = 2 * k + 1;
//	while (l < r) {
//		mid = (l + r) >> 1;
//		if (check2(mid)) {
//			r = mid;
//		}
//		else {
//			l = mid + 1;
//		}
//	}
//	cout << l << '\n';
//}


//int n, a, b;
//int ans[666];
//bool vis[666];
//void solve() {
//	cin >> n >> a >> b;
//	for (int i = 1; i <= n; i++)vis[i] = 0;
//	int cur = n;
//	for (int i = 1; i < n / 2; i++, cur--) {
//		if (cur == b)cur--;
//		if (cur == a) {
//			cout << -1 << '\n';
//			return;
//		}
//		ans[i] = cur;
//		vis[cur] = 1;
//	}
//	ans[n / 2] = a;
//	vis[a] = 1;
//	cur = 1;
//	for (int i = n / 2 + 1; i <= n; i++, cur++) {
//		while (vis[cur])cur++;
//		ans[i] = cur;
//	}
//	for (int i = 1; i <= n / 2; i++) {
//		if (min(ans[i], a) != a) {
//			cout << -1 << '\n';
//			return;
//		}
//	}
//	for (int i = n / 2 + 1; i <= n; i++) {
//		if (max(ans[i], b) != b) {
//			cout << -1 << '\n';
//			return;
//		}
//	}
//	for (int i = 1; i <= n; i++) {
//		cout << ans[i] << ' ';
//	}
//	cout << '\n';
//}
//void solve() {
//	int x, y;
//	cin >> x >> y;
//	if ((x + y) & 1) {
//		cout << -1 << ' ' << -1 << '\n';
//		return;
//	}
//	if (x & 1) {
//		cout << x / 2 << ' ' << (y + 1) / 2 << '\n';
//	}
//	else {
//		cout << x / 2 << ' ' << y / 2 << '\n';
//	}
//}

//int ans;
//int n;
//struct edge
//{
//	int u, v, w;
//	bool operator<(const edge& x) const {
//		return w < x.w;
//	}
//}e[6010];
//
//int f[6010], s[6010];
//int find(int x) {
//	return x == f[x] ? x : f[x] = find(f[x]);
//}
//
//void solve() {
//	cin >> n;
//	for (int i = 1, u, v, w; i < n; i++) {
//		cin >> u >> v >> w;
//		e[i].u = u, e[i].v = v, e[i].w = w;
//	}
//	sort(e + 1, e + n);
//	for (int i = 1; i <= n; i++)f[i] = i, s[i] = 1;
//	ans = 0;
//	for (int i = 1; i < n; i++) {
//		int u = e[i].u, v = e[i].v, w = e[i].w;
//		int fu = find(u), fv = find(v);
//		if (fu == fv)continue;
//		ans += (w + 1) * (s[fu] * s[fv] - 1);
//		f[fu] = fv;
//		s[fv] += s[fu];
//	}
//	cout << ans << '\n';
//}
//
//int t;
//cin >> t;
//while (t--) {
//	solve();
//}
//
//cin >> n >> m;
//
//for (int i = 1, x, y, z; i <= m; i++) {
//	cin >> x >> y >> z;
//	add(x, y, z); add(y, x, z);
//}
//
//vector <int> ans;
//cin >> s;
//dj(s);
//int sum = 0;
//for (int i = 1; i <= n; i++) {
//	if (i == s)continue;
//	sum += w[pre[i]];
//	ans.push_back((pre[i] + 1) / 2);
//}
//sort(ans.begin(), ans.end());
//cout << sum << '\n';
//for (auto x : ans) {
//	cout << x << " ";
//}

//int head[300005], nxt[600005], to[600005], w[600005], pre[600005];
//int n, m, cnt, s;
//int dis[300005];
//bool vis[300005];
//void add(int u, int v, int z) {
//	nxt[++cnt] = head[u];
//	head[u] = cnt;
//	to[cnt] = v;
//	w[cnt] = z;
//}
//
//struct node
//{
//	int v, dis;
//	bool operator<(const node& x)const {
//		return x.dis < dis;
//	}
//};
//
//void dj(int s) {
//	for (int i = 1; i <= n; i++) {
//		dis[i] = INF;
//	}
//
//	priority_queue<node> q;
//	dis[s] = 0;
//	q.push({ s,0 });
//	while (!q.empty()) {
//		auto tmp = q.top(); q.pop();
//		int u = tmp.v;
//		if (vis[u])continue;
//		vis[u] = 1;
//		for (int i = head[u]; i; i = nxt[i]) {
//			int v = to[i], wi = w[i];
//			if (!vis[v] && dis[v] > dis[u] + wi) {
//				dis[v] = dis[u] + wi;
//				q.push({ v,dis[v] });
//				pre[v] = i;
//			}
//			if (dis[u] + wi == dis[v] && w[pre[v]] > wi) {
//				pre[v] = i;
//			}
//		}
//	}
//}
